package 图;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/13 18:09
 */
public class lc743网络延迟时间 {


    public int networkDelayTime(int[][] times, int n, int k) {
        int ans = 0;
        HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<>(n + 1);
        /*
         初始化图的时候，是有问题的！
         */
        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashMap<>());
        }
        for (int time[] : times) {
            graph.computeIfAbsent(time[0], t -> new HashMap<>()).put(time[1], time[2]);
//            graph.get(time[0]).put(time[1],time[2]);
        }

        int dist[] = new int[n + 1];
        boolean vis[] = new boolean[n + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        queue.add(new int[]{k, 0});

        while (!queue.isEmpty()) {
            int curArr[] = queue.remove();
            int curNode = curArr[0];
            int curValue = curArr[1];
            // 开始遍历邻接点
            for (Map.Entry<Integer, Integer> next : graph.get(curNode).entrySet()) {
                if (!vis[curNode] && curValue + next.getValue() < dist[next.getKey()]) {
                    dist[next.getKey()] = curValue + next.getValue();
                    queue.add(new int[]{next.getKey(), dist[next.getKey()]});
                }
            }
            vis[curNode] = true;  // 只要 把 curNode 当前的邻接点 给计算完毕的话, 就把当前节点给加入到, vis 数组中, 表示当前这个节点已经锁死

        }
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }

        return ans;
    }


    /*
     独自写不一定能够写的对!

     多写, 多熟练, 因为 你不一定能够一次写对!

     */
    public int netwoek(int[][] times, int n, int k) {
        int ans = 0;
        HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashMap<>());  //初始化图
        }
        //建图
        for (int time[] : times) {
//            graph.get()
            graph.computeIfAbsent(time[0], t -> new HashMap<>()).put(time[1], time[2]);
        }

        // 开始 跑 最短路算法 dijkstra（没有负边）

        int dist[] = new int[n + 1]; //  单源最短路径记录数组

        Arrays.fill(dist, Integer.MAX_VALUE); // 刚开始所有点， 距离无穷大，
        // 自己到自己的距离为 0
        dist[k] = 0;

        boolean[] vis = new boolean[n + 1]; //表示 已经锁死的 节点，


        // 小根堆的排序规则
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 这里的泛型， 主要能表示一个键值对就行， 用 Map.Entry 也行, 但是没必要, 直接用 int[] 可以

        queue.add(new int[]{k, 0});  //这里细节别忘了

        while (!queue.isEmpty()) {
            int[] remove = queue.remove(); // 主要是这个键值对数组的理解!
            // remove[0] : 表示 节点,  remove[1] 表示的是距离
            for (Map.Entry<Integer, Integer> next : graph.get(remove[0]).entrySet()) { // 遍历当前节点的后续节点!
                int dis;                            //  remove[1] = dist[remove[0]] , 表示什么意思不言而喻了, 小根堆存储的 key- value 是什么也不言而喻了吧
                if (!vis[remove[0]] && (dis = next.getValue() + dist[remove[0]]) < dist[next.getKey()]) {
                    dist[next.getKey()] = dis;
                    queue.add(new int[]{next.getKey(), dis}); // 这个 可别漏掉!
                }
//  上面的 if 判断 可以改成下面的 这 两个 if ,但是 常数 时间复杂度很高, 因为 进行了很多无用的操作! , 这一点要注意!

                // if(!vis[remove[0]]){
                //     dist[next.getKey()] = Math.min(next.getValue() + remove[1],dist[next.getKey()]);
                //     queue.add(new int []{next.getKey(),dist[next.getKey()]});
                // }


                //    if(!vis[remove[0]]){
                //     dist[next.getKey()] = Math.min(next.getValue() + dist[remove[0]],dist[next.getKey()]);
                //     queue.add(new int []{next.getKey(),dist[next.getKey()]});
                // }

            }
            vis[remove[0]] = true;
        }

        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) { // 说明有点达到不到
                return -1; // 题目要求的
            }
            ans = Math.max(ans, dist[i]);
        }

        return ans;
    }


    /*
     首先这个 最短路的算法， 你要写的很熟悉的，
     要不然你都无法进行解题的！
     */
    public int dijkstra(int edges[][], int n, int k) {
        int ans = 0;

        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>(n);
        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashMap<>());
        }
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], t -> new HashMap<>()).put(edge[1], edge[2]);
        }


        boolean vis[] = new boolean[n + 1];

        int dist[] = new int[n + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);


        dist[k] = 0;
        queue.add(new int[]{k, 0});// 这里面存储的 就是 当前的 dist[k]
        while (!queue.isEmpty()) {
            int[] remove = queue.remove();

            for (Map.Entry<Integer, Integer> next : graph.get(remove[0]).entrySet()) {
                int dis = remove[1] + next.getValue();
                if (!vis[next.getKey()] && dis < dist[next.getKey()]) {
                    dist[next.getKey()] = dis;
                    queue.add(new int[]{next.getKey(), dis});
                }

            }
            vis[remove[0]] = true;

        }
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }


        return ans;
    }


    public int dij(int edges[][], int n, int k) {
        HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            graph.put(i, new HashMap<>());
        }
        for (int i = 0; i < edges.length; i++) {
            int edge[] = edges[i];
            graph.get(edge[0]).put(edge[1], edge[2]); // 有向图
        }

        int dist[] = new int[n + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[k] = 0;

        boolean vis[] = new boolean[n + 1];

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        queue.add(new int[]{k, 0});
        while (!queue.isEmpty()) {
            int[] remove = queue.remove();
            int cur = remove[0];

            for (Map.Entry<Integer, Integer> next : graph.get(cur).entrySet()) {
                if (vis[next.getKey()]) {
                    continue;
                }
                if (remove[1] + next.getValue() < dist[next.getKey()]) {
                    dist[next.getKey()] = remove[1] + next.getValue();
                    queue.add(new int[]{next.getKey(), dist[next.getKey()]});
                }


            }
            vis[cur] = true;
        }
        int ans = 0;
        dist[0] = -1; // 0  号 点, 是不合法点
        for (int num : dist) {
            if (num == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, num);
        }
        return ans;
    }




}
